Adityawarman turut serta dalam ekspansi Majapahit ke Bali pada tahun 1343 yang dipimpin oleh Gajah Mada. Dalam catatan Babad Arya Tabanan, disebutkan bahwa Gajah Mada dibantu seorang ksatria keturunan Kediri bernama Arya Damar disebutkan juga sebagai penguasa Palembang[9], yang merupakan nama alias Adityawarman[10]. Diceritakan bahwa ia dan saudara-saudaranya membantu Gajah Mada memimpin pasukan-pasukan Majapahit untuk menyerbu Pejeng, Gianyar, yang merupakan pusat Kerajaan Bedahulu, dari berbagai penjuru. Kerajaan Bedahulu adalah kerajaan kuno yang berdiri sejak abad ke-8 sampai abad ke-14 di pulau Bali, dan diperintah oleh raja-raja keturunan dinasti Warmadewa.

Pertempuran yang terjadi berakhir dengan kekalahan Bedahulu, dan patih Bedahulu Kebo Iwa gugur sementara raja Sri Astasura Ratna Bumi Banten pergi mengasingkan diri. Setelah Bali berhasil ditaklukan, Arya Damar kembali ke Majapahit dan diangkat menjadi raja di Palembang. Sebagian saudara-saudara Arya Damar (beberapa catatan menyebutkan putra putranya nya) ada yang menetap di Bali, dan di kemudian hari salah seorang keturunannya Arya Kenceng mendirikan Kerajaan Tabanan dan Kerajaan Badung di Denpasar.